package SwordFingerOffer;

public class Q42_MaxSubArray {
    //连续子数组最大和

    public int maxSubArray(int[] nums) {

        int res = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //计算累加和
            sum += nums[i];
            //维持住最大值
            res = Math.max(sum, res);
            //小于 0 废除重新来 ==> -3 1 ==> -3 -2 ==> max == -2
            //最大值已记录不会错过
            if (sum < 0) {
                sum = 0;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Q42_MaxSubArray fun = new Q42_MaxSubArray();
        System.out.println(fun.maxSubArray(new int[]{-2, 1}));
    }
}
